//
//$Id: fa.cpp 687 2011-03-13 12:21:29Z andrew.tsyganov $
#include "stdafx.h"

#include "include/fa_utils.h"
#include "include/re.h"
#include "include/re2fa.h"
#include "include/utils.h"
#include "include/sets.h"
#include "include/my_time.h"
#include "contrib/rapidxml/rapidxml.hpp"
#include "contrib/rapidxml/rapidxml_print.hpp"
#include "src/heo/include/sys_api.h"
#include <sstream>
#include <stack>
#include <map>
#include <numeric>
#include <algorithm>

#if defined(_WIN32)
#include "include/dirent.h"
#else
#include <dirent.h>
#endif

using namespace std;

///////////////////////////////////////////////////////////////////////////////
// Procedures and functions for automata manipulations ////////////////////////
///////////////////////////////////////////////////////////////////////////////

// Reverse automaton
// input:  fa  - finite automaton
// output: rfa - reverse of fa
void Reverse(FA const& fa, FA& rfa)
{
	u_t m = fa.get_Symbols_Num(); 
	u_t n = fa.get_States_Num(); 
	
	rfa.init("rev(" + fa.get_Name() + ")", m, n);
	rfa.set_Symbols(fa.get_Symbols());
	rfa.set_States(fa.get_States());

	rfa.set_Initial(fa.get_Final());
	rfa.set_Final(fa.get_Initial());

    for (u_t i = 0; i < n; ++i)
    {
		vector<Adjacent> const& delta = fa.get_Delta();
		for (Adjacent::const_iterator it_t = delta[i].begin(); it_t != delta[i].end(); ++it_t)
        {
			for (Subset::const_iterator it_s = it_t->second.begin(); it_s != it_t->second.end(); ++it_s)
			{
				rfa.add_Transition(*it_s, it_t->first, i);
			}
        }
    }
}

// Determinization (subset construction)
// input:  fa    - finite automaton (determinstic or nondeterministic)
// output: dfa   - dense deterministic automaton
// output: vs_fa - subsets of fa states  
void Determinize(FA const& fa, FA& dfa, std::vector<Subset>& vs_fa)
{
    vs_fa.clear();

	u_t m = fa.get_Symbols_Num(); 
	u_t n = fa.get_States_Num(); 
	
	dfa.init("det(" + fa.get_Name() + ")", m, 0);
	dfa.set_Symbols(fa.get_Symbols());

	if (n == 0)
	{
		return;
	}

	map<u_t, Subset> hash_table;
	map<u_t, Subset>::iterator hash_iterator;
    BitSet hash_history;
	u_t curr_id, dst_id, hash_code;
	
	bool eps = fa.is_Epsilon();

	curr_id = dfa.add_State(); // curr_id = 0;
	dfa.set_Initial(curr_id);
	vs_fa.push_back(eps ? fa.epsilon_Closure(fa.get_Initial()) : fa.get_Initial());
	hash_code = vs_fa[curr_id].calc_Hash();
	hash_history.insert(hash_code);
	hash_table[hash_code].insert(curr_id);;

	//double part_time = 0;

	while (curr_id < dfa.get_States_Num())
	{
		for (u_t j = 0; j < m; ++j)
		{
			Subset dst = eps ? fa.epsilon_Closure(fa.move(vs_fa[curr_id], j)) : fa.move(vs_fa[curr_id], j);
			hash_code = dst.calc_Hash();

			if (!hash_history.contains(hash_code))
			{
                //double start_time = get_time();
				dst_id = dfa.add_State();
				vs_fa.push_back(dst);
				hash_table[hash_code].insert(dst_id);
				hash_history.insert(hash_code);
                //double end_time = get_time();
			    //part_time += (end_time-start_time);
			}
			else
			{
				hash_iterator = hash_table.find(hash_code);
				
				bool found = false;

				for (Subset::const_iterator it = hash_iterator->second.begin(); it != hash_iterator->second.end(); ++it)
				{
					if (vs_fa[*it] == dst)
					{
						dst_id = *it;
						found = true;
						break;
					}
				}

				if (!found)
				{
					dst_id = dfa.add_State();
					vs_fa.push_back(dst);
					hash_iterator->second.insert(dst_id);
				}
			}

			dfa.add_Transition(curr_id, j, dst_id);
		}

		++curr_id;
	}

	//cout << "part time = " << part_time << " s" << endl;

	// determine final states
    for (u_t i = 0; i < vs_fa.size(); ++i)
    {
        for (Subset::const_iterator it = vs_fa[i].begin(); it != vs_fa[i].end(); ++it)
        {
			if (fa.is_Final(*it))
            {
				dfa.set_Final(i);
                break;
            }
        }
    }
}

// Check wheher two dense DFAs are isomorphic
// input:  dfa1, dfa2 - two determinstic finite automata
// output: vs         - vector of states correspondence (vs[i] == j means that state i of dfa1 corresponds to state j in dfa2)
bool AreIsomorphicDFAs(FA const& dfa1, FA const& dfa2, std::vector<u_t>& vu)
{
    u_t n1 = dfa1.get_States_Num();
	u_t n2 = dfa2.get_States_Num();

	u_t m1 = dfa1.get_Symbols_Num();
    u_t m2 = dfa2.get_Symbols_Num();

	u_t f1 = dfa1.get_Final_Num();
    u_t f2 = dfa2.get_Final_Num();

    if ((n1 != n2) || (m1 != m2) || (f1 != f2))
	{
        return false;
	}

    vu.clear();
    vu.resize(n1, n1); // init elements with states number
    
    vector<u_t> list;
    list.reserve(n1);

	Subset const& dfa1_in = dfa1.get_Initial();
	Subset const& dfa2_in = dfa2.get_Initial();

	vector<Adjacent> const& dfa1_delta = dfa1.get_Delta();
	vector<Adjacent> const& dfa2_delta = dfa2.get_Delta();

	u_t in1_id = *dfa1_in.begin();
    vu[in1_id] = *dfa2_in.begin();
    list.push_back(in1_id);

    while (!list.empty())
    {
        u_t src1_id = list.back();
        list.pop_back();

        u_t src2_id = vu[src1_id];

        for (u_t j = 0; j < m1; ++j)
        {
            u_t dest1_id = *(dfa1_delta[src1_id].find(j)->second.begin());
            u_t dest2_id = *(dfa2_delta[src2_id].find(j)->second.begin());

            bool is_fin1 = dfa1.is_Final(dest1_id);
            bool is_fin2 = dfa2.is_Final(dest2_id);

            if ((is_fin1 && !is_fin2) || (!is_fin1 && is_fin2))
			{
                return false;
			}

            if (vu[dest1_id] == n1)
            {
                vu[dest1_id] = dest2_id;
                list.push_back(dest1_id);
                continue;
            }

            if (vu[dest1_id] != dest2_id)
			{
                return false;
			}
        }
    }

    return true;
}

// Check whether two dense DFAs are equivalent using Hopcroft-Karp algorithm
bool AreEquivalentDFAs(FA const& dfa1, FA const& dfa2)
{
	u_t m  = dfa1.get_Symbols_Num();

    if (dfa2.get_Symbols_Num() != m)
	{
        return false;
	}

    vector<Subset>      sets;
    vector<States_Pair> list;
    Subset              available_sets;

	u_t n1 = dfa1.get_States_Num();
    u_t n2 = dfa2.get_States_Num();
    u_t n_sum = n1 + n2;
    
    sets.resize(n_sum);
    list.reserve(n_sum);
    available_sets.insert_range(0, n_sum - 1);
   
    for (u_t i = 0; i < n_sum; ++i)
    {
        sets[i].insert(i); 
    }

    //PrintSets(sets, available_sets);

	Subset const& dfa1_in = dfa1.get_Initial();
	Subset const& dfa2_in = dfa2.get_Initial();

	vector<Adjacent> const& dfa1_delta = dfa1.get_Delta();
	vector<Adjacent> const& dfa2_delta = dfa2.get_Delta();

	u_t in1 = *dfa1_in.begin();
	u_t in2 = n1 + *dfa2_in.begin();

    Merge(sets, available_sets, in1, in2);
	
	//PrintSets(sets, available_sets);

    States_Pair sp(in1, in2);
    list.push_back(sp);

    //double start_time, end_time;

    while (!list.empty())
    {
        sp = list.back();
        list.pop_back();

        //cout << "Pop up pair (" << sp.first_ << "," << sp.second_ << ")" << endl;

        for (u_t k = 0; k < m; ++k)
        {
            //cout << "Symbol: " << k << endl;

            //start_time = get_time();

            u_t r1;

            if (sp.first_ < n1)
            {
                r1 = Find(sets, available_sets, *(dfa1_delta[sp.first_].get_Dst(k).begin()));
            }
            else
            {
                r1 = Find(sets, available_sets, n1 + *(dfa2_delta[sp.first_ - n1].get_Dst(k).begin()));
            }
                    
            size_t r2;

            if (sp.second_ < n1)
            {
                r2 = Find(sets, available_sets, *(dfa1_delta[sp.second_].get_Dst(k).begin()));
            }
            else
            {
                r2 = Find(sets, available_sets, n1 + *(dfa2_delta[sp.second_ - n1].get_Dst(k).begin()));
            }

            //end_time = get_time();

            //cout << "find time = " << end_time - start_time << endl;

            //cout << "r1 = " << r1 << ", r2 = " << r2 << endl;

            if (r1 != r2)
            {
                //cout << "Merging subsets " << r1 << " and " << r2 << endl;

                //start_time = get_time();
                Merge(sets, available_sets, r1, r2);
                //end_time = get_time();
                //cout << "merge time = " << end_time - start_time << endl;
    
                States_Pair t(r1, r2);
                //cout << "Push down pair (" << t.first_ << "," << t.second_ << ")" << endl;
                
                list.push_back(t);
            }

            //PrintSets(sets, available_sets);
        }
    }

	for (Subset::const_iterator it_av = available_sets.begin(); it_av != available_sets.end(); ++it_av)
    {
        //start_time = get_time();
        //cout << sets[*it_av].to_String() << endl;
        u_t sum = 0;
		for (Subset::const_iterator it = sets[*it_av].begin(); it != sets[*it_av].end(); ++it)
        {
            u_t state_id = *it;
            if (state_id < n1) 
            {
				if (dfa1.is_Final(state_id))
				{
                    ++sum;
				}
            }
            else
            {
                if (dfa2.is_Final(state_id - n1))
				{
                    ++sum;
				}
            }
        }

        //end_time = get_time();
        //cout << "subset traversing time = " << end_time - start_time << endl;
        if ((sum != 0) && (sum != sets[*it_av].size()))
		{
            return false;
		}
    }

    return true;
}

// Check whether two FAs are equivalent
bool AreEquivalentFAs(FA const& fa1, FA const& fa2)
{
	FA dfa1, dfa2;

	if (!fa1.is_Deterministic())
	{
		vector<Subset> vs;
		Determinize(fa1, dfa1, vs);
	}
	else
	{
		dfa1 = fa1;
		if (!dfa1.is_Dense()) 
		{
			dfa1.make_Dense();
		}
	}

	if (!fa2.is_Deterministic())
	{
		vector<Subset> vs;
		Determinize(fa2, dfa2, vs);
	}
	else
	{
		dfa2 = fa2;
		if (!dfa2.is_Dense()) 
		{
			dfa2.make_Dense();
		}
	}

	return AreEquivalentDFAs(dfa1, dfa2);
}

// Brzozowski's minimization algorithm
// input:  fa   - finite automaton (deterministic or nondeterministic)
// output: mdfa - minimal deterministic finite automaton 
void MinimizeBrzozowski(FA const& fa, FA& mdfa)
{
	// TODO: clear memory for unused objects  
    FA rfa, drfa, rdrfa;
    vector<Subset> vs_rfa, vs_rdrfa;

    Reverse(fa, rfa);
    Determinize(rfa, drfa, vs_rfa);
     
    Reverse(drfa, rdrfa);
    Determinize(rdrfa, mdfa, vs_rdrfa);
}

// Hopcroft's DFA minimization algorithm 
// input:  dfa    - deterministic finite automaton
// input:  rdfa   - reverse of dfa 
// output: mdfa   - minimal deterministic finite automaton
// output: vs_dfa - subsets of dfa
void MinimizeHopcroft(FA const& dfa, FA const& rdfa, FA& mdfa, vector<Subset>& vs_dfa)
{
    Subset t;
    vector<Subset>  l;
    vector<Subset>& p = vs_dfa;

    u_t n = dfa.get_States_Num();
    u_t k = dfa.get_Symbols_Num();
    
    p.reserve(n);
    l.reserve(n);

    // split dfa states into two subsets
    t.insert_range(0, n - 1);
    t -= dfa.get_Final();

    if (dfa.get_Final_Num() < t.size())
    {
        l.push_back(dfa.get_Final());
    }
    else
    {
        if(!t.empty())
        {
            l.push_back(t);
        }
    }

    p.push_back(dfa.get_Final());
    if (!t.empty())
    {
        p.push_back(t);
    }

    //cout << ">>>>>> p = ";
    //PrintVector(cout, p);

    //cout << ">>>>>> l = ";
    //PrintVector(cout, l);

	vector<Adjacent> const& rdfa_delta = rdfa.get_Delta();

	while (!l.empty())
    {
        Subset c = l.back();
        l.pop_back();
        //cout << endl
        //     << "c = " << c.to_String() << endl;

        //cout << ">>>>>> l = ";
        //PrintVector(cout, l);

        for (size_t j = 0; j < k; ++j)
        {
            //cout << endl
            //     << "------ sym = " << j << " ------" << endl;

            Subset inv;

			for (Subset::const_iterator it = c.begin(); it != c.end(); ++it)
            {
				if (rdfa_delta[*it].contains(j))
				{
					inv |= rdfa_delta[*it].get_Dst(j);
				}
            }

            //cout << "inv = " << inv.to_String() << endl;

            size_t i = 0;
            while (i < p.size())
            {
                //cout << endl
                //     << "i = " << i << endl;
                //cout << "p[" << i << "] = " << p[i].to_String() << endl;

                Subset b1 = p[i];
				Subset b2 = p[i];

                b1 &= inv;
                b2 -= b1;

                //cout << "b1 = " << b1.to_String() << endl;
                //cout << "b2 = " << b2.to_String() << endl;
                
                if ((!b1.empty()) && (!b2.empty()))
                {
                    if (b1.size() < b2.size())
                    {
                        p[i] = b2;
                        p.push_back(b1);
                        l.push_back(b1);
                    }
                    else
                    {
                        p[i] = b1;
                        p.push_back(b2);
                        l.push_back(b2);
                    }

                    //cout << ">>>>>> p = ";
                    //PrintVector(cout, p);

                    //cout << ">>>>>> l = ";
                    //PrintVector(cout, l);
             }

                ++i;
            }
        }
    }

    //cout << endl
    //     << "Final subsets: ";
    //PrintVector(cout, p);

    n = p.size();

	mdfa.init("min(" + dfa.get_Name() + ")", k, n);
    mdfa.set_Symbols(dfa.get_Symbols());
    
	vector<Adjacent> const& dfa_delta = dfa.get_Delta();

	// construct mdfa transitions
    for (u_t i = 0; i < n; ++i)
    {
        u_t src_id = *(p[i].begin());

        for (u_t j = 0; j < k; ++j)
        {
            if (dfa_delta[src_id].contains(j))
            {
                u_t dst_id = *(dfa_delta[src_id].get_Dst(j).begin());
                for (u_t q = 0; q < n; ++q)
                {
                    if (p[q].contains(dst_id))
                    {
                        mdfa.add_Transition(i, j, q);
                        break;
                    }
                }
            }
        }
    }

    // determine initial and final states
    for (u_t i = 0; i < n; ++i)
    {
        for (Subset::const_iterator it = p[i].begin(); it != p[i].end(); ++it)
        {
            if (dfa.is_Initial(*it))
            {
                mdfa.set_Initial(i);
            }

            if (dfa.is_Final(*it))
            {
                mdfa.set_Final(i);
            }
        }
    }
}


///////////////////////////////////////////////////////////////////////////////
// Utilities for Hopcroft-Karp algorithm //////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////

// Merge sets i and j
inline void Merge(vector<Subset>& sets, Subset& available_sets, u_t i, u_t j)
{
    sets[j] |= sets[i];
    available_sets.remove(i);
}

// Find set containing state i
inline u_t Find(vector<Subset> const& sets, Subset const& available_sets, u_t i)
{
	for (Subset::const_iterator it = available_sets.begin(); it != available_sets.end(); ++it)
	{
        if (sets[*it].contains(i))
		{
            return *it;
		}
	}
#ifdef _MSC_VER
    __assume(0);
#endif
}

// Print sets (debug)
void PrintSets(vector<Subset> const& sets, Subset const& available_sets)
{
	for (Subset::const_iterator it = available_sets.begin(); it != available_sets.end(); ++it)
	{
        cout << sets[*it].to_String() << *it << " " << flush;
	}
    cout << endl << flush;
}

// Get FA from XML file containing either FA or RE node
bool GetFA(std::string const& file, FA& fa)
{
	fa.clear();

	if (HasFANode(file))
	{
		return fa.load_XML(file);
	}
	else
	{
		if (HasRENode(file))
		{
			RE re;
			if (!re.load_XML(file))
			{
				return false;
			}
			REToFA(re, fa);
			return true;
		}
		else
		{
			return false;
		}
	}
}

///////////////////////////////////////////////////////////////////////////////
// Subautomata routines ///////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////

void GetSubAutomatonByStates(FA const& a, Subset const& s, FA& sa)
{
	if (s.empty())
	{
		return;
	}

	Subset::const_reverse_iterator rit = s.rbegin();

	if (*rit > a.get_States_Num())
	{
		cout << "GetSubAutomatonByStates error: incorrect set of states!" << endl;
		return;
	}

	u_t n = s.size();
	u_t m = a.get_Symbols_Num();

    sa.init("sub(" + a.get_Name() + ")", m, n);

	map<u_t, u_t> ids;

	u_t k = 0;
	for (Subset::const_iterator it = s.begin(); it != s.end(); ++it)
	{
		ids[*it] = k;

		if (a.is_Initial(*it))
		{
			sa.set_Initial(k);
		}

		if (a.is_Final(*it))
		{
			sa.set_Final(k);
		}

		++k;
	}

	vector<Adjacent> const& delta = a.get_Delta();
	for (map<u_t, u_t>::const_iterator m_it = ids.begin(); m_it != ids.end(); ++m_it)
	{
		for (u_t j = 0; j < m; ++j)
		{
			Subset const& s_dst = delta[m_it->first].get_Dst(j);
			for (Subset::const_iterator s_it = s_dst.begin(); s_it != s_dst.end(); ++s_it)
			{
				map<u_t, u_t>::const_iterator it = ids.find(*s_it);
				if (it != ids.end())
				{
					sa.add_Transition(m_it->second, j, it->second);
				}
			}
		}
	}
}

void ConvertToTransitionsVector(FA const& a, vector<Transition>& vt)
{
	vt.clear();
	vector<Adjacent> const& delta = a.get_Delta();
	vt.reserve(a.get_Transitions_Num());

	for (u_t i = 0; i < delta.size(); ++i)
	{
		for (Adjacent::const_iterator a_it = delta[i].begin(); a_it != delta[i].end(); ++a_it)
		{
			for (Subset::const_iterator dst_it = a_it->second.begin(); dst_it != a_it->second.end(); ++dst_it)
			{
				Transition t(i, a_it->first, *dst_it);
				vt.push_back(t);
			}
		}
	}
}

void GetSubAutomatonByTransitions(string const& name, vector<Transition> const& vt, Subset const& in, Subset const& fin, Subset const& s, FA& sa)
{
	/*
	if (s.empty())
	{
		return;
	}

	Subset::const_reverse_iterator rit = s.rbegin();

	if (*rit >= vt.size())
	{
		cout << "GetSubAutomatonByStates error: incorrect set of transitions!" << endl;
		return;
	}

	Subset states;

	for (Subset::const_iterator s_it = s.begin(); s_it != s.end(); ++s_it)
	{
		states.insert(vt[*s_it].src_id_);
		states.insert(vt[*s_it].dst_id_);
	}

	u_t n = states.size();
	u_t m = a.get_Symbols_Num();

    sa.init("sub(" + name + ")", m, n);

	map<u_t, u_t> ids;

	u_t k = 0;
	for (Subset::const_iterator it = s.begin(); it != s.end(); ++it)
	{
		ids[*it] = k;

		if (a.is_Initial(*it))
		{
			sa.set_Initial(k);
		}

		if (a.is_Final(*it))
		{
			sa.set_Final(k);
		}

		++k;
	}
	*/
}

///////////////////////////////////////////////////////////////////////////////
// Batch load and save automata ///////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////

// Load automata to vector
bool LoadFAs(vector<FA>& v_fa, string const& dir)
{
    DIR *dp;
    struct dirent *dirp;
    if ((dp  = opendir(dir.c_str())) == NULL) 
    {
        cout << "LoadFAs: error opening " << dir << endl;
        return false;
    }

    //v_fa.reserve(1000);

    while ((dirp = readdir(dp)) != NULL) 
    {
        string fname(dirp->d_name); 
        
        if (GetFileExtension(fname) != "xml")
		{
            continue;
		}

		string file = CreatePath(dir, fname);

		if (HasFANode(file))
		{
			FA fa;

			if (fa.load_XML(CreatePath(dir, fname)))
			{
				v_fa.push_back(fa);
			}
		}
    }

    closedir(dp);

    return true;
}

// Load automata and rational expressions converted to automata to vector
bool LoadFAsREs(vector<FA>& v_fa, string const& dir)
{
    DIR *dp;
    struct dirent *dirp;
    if ((dp  = opendir(dir.c_str())) == NULL) 
    {
        cout << "LoadFAs: error opening " << dir << endl;
        return false;
    }

    //v_fa.reserve(1000);

    while ((dirp = readdir(dp)) != NULL) 
    {
        string fname(dirp->d_name); 
        
        if (GetFileExtension(fname) != "xml")
		{
            continue;
		}

		string file = CreatePath(dir, fname);

		FA fa;
		if (GetFA(file, fa))
		{
			v_fa.push_back(fa);
		}
    }

    closedir(dp);

    return true;
}

// Save automata from vector
bool SaveFAs(vector<FA>& v_fa, string const& dir)
{
    bool save_OK = true;

    for (size_t i = 0; i < v_fa.size(); ++i)
	{
        save_OK &= v_fa[i].save_XML(CreatePath(dir, v_fa[i].get_Name() + ".xml"));
	}

    return save_OK;
}

//EOF!
